home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / bplus25a.zip / BPLUS.C < prev    next >
Text File  |  1991-06-14  |  26KB  |  1,004 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 2.5            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                    Copyright (C) 1987-1991 by                    */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7900 Edgewater Drive                        */
  12. /*                      Wilsonville, Oregon  97070                  */
  13. /*                      (503) 694 - 1449                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. #include <process.h>
  22. #include <sys\types.h>            /*  delete this line for Turbo C  */
  23. #include <sys\stat.h>
  24. #include <string.h>
  25. #include "bplus.h"
  26.  
  27.  
  28. /*  macros, constants, data types  */
  29.  
  30. #define  NULLREC      (-1L)
  31. #define  FREE_BLOCK   (-2)
  32.  
  33. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  34. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  35. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  36. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  37. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  38. #define  BUFCOUNT(j)      (mci->cache[j].count)
  39. #define  CB(j)            (pci->pos[j].cblock)
  40. #define  CO(j)            (pci->pos[j].coffset)
  41. #define  TRUE             1
  42. #define  FALSE            0
  43.  
  44.                                     /* BPLUS uses the library routine    */
  45.                                     /* memmove which must be used with   */
  46.                     /* Turboc 1.5, 2.0, Quick C and      */
  47.                     /* MS C 5.0 and 5.1                  */
  48. /* #define memmove    memcpy */     /* Use this macro for Microsoft C4.0 */
  49.  
  50. /*  declare some global variables  */
  51.  
  52. IX_DESC      *pci;
  53. IX_BUFFER    bt_buffer;
  54. IX_BUFFER    *mci = &bt_buffer;
  55. BLOCK        *block_ptr;
  56. BLOCK        *spare_block;
  57. int          cache_ptr = 0;
  58. int          cache_init = 0;
  59. int          split_size = IXB_SPACE;
  60. int          comb_size  = (IXB_SPACE/2);
  61.  
  62. void pascal error(int, long);
  63. void pascal read_if(long, char *, int);
  64. void pascal write_if(int, long, char *, int);
  65. void pascal reset_buffers(IX_DESC *);
  66. int  pascal creat_if(char *);
  67. int  pascal open_if(char *);
  68. void pascal close_if(int);
  69. void pascal update_block(void);
  70. void pascal init_cache(void);
  71. int  pascal find_cache(RECPOS);
  72. int  pascal new_cache(void);
  73. void pascal load_cache(RECPOS);
  74. void pascal get_cache(RECPOS);
  75. void pascal retrieve_block(int, RECPOS);
  76. int  pascal prev_entry(int);
  77. int  pascal next_entry(int);
  78. void pascal copy_entry(ENTRY *, ENTRY *);
  79. int  pascal scan_blk(int);
  80. int  pascal last_entry(void);
  81. void pascal write_free( RECPOS, BLOCK *);
  82. RECPOS pascal get_free(void);
  83. int  pascal find_block(ENTRY *, int *, int *);
  84. void pascal movedown(BLOCK *, int, int);
  85. void pascal moveup(BLOCK *, int, int);
  86. void pascal ins_block(BLOCK *, ENTRY *, int);
  87. void pascal del_block(BLOCK *, int);
  88. void pascal split(int, ENTRY *, ENTRY *);
  89. void pascal ins_level(int, ENTRY *);
  90. int  pascal insert_ix(ENTRY *, IX_DESC *);
  91. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  92. int  pascal combineblk(RECPOS, int);
  93. void pascal replace_entry(ENTRY *);
  94. void print_blk(BLOCK *);
  95.  
  96.  
  97. /*  file I/O for B-PLUS module  */
  98.  
  99. void pascal error(j, l)
  100.   int j;
  101.   long l;
  102.   {
  103.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  104.                            "ERROR WHILE READING FILE",
  105.                            "ERROR WHILE WRITING FILE"};
  106.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  107.     exit(1);
  108.   } /* error */
  109.  
  110.  
  111. void pascal read_if(start, buf, nwrt)
  112.   long start;
  113.   char *buf;
  114.   int nwrt;
  115.   {
  116.     long err;
  117.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  118.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  119.     if (err != 0) error(1, start);
  120.   } /* read_if */
  121.  
  122.  
  123. void pascal write_if(handle, start, buf, nwrt)
  124.   int handle;
  125.   long start;
  126.   char *buf;
  127.   int nwrt;
  128.   {
  129.     long err;
  130.     err = start - lseek(handle, start, SEEK_SET);
  131.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  132.     if (err != 0) error(2, start);
  133.   } /* write_if */
  134.  
  135.  
  136. int pascal creat_if(fn)
  137.   char *fn;
  138.   {
  139.     int   ret;
  140.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  141.     if (ret  < 0) error(0,0L);
  142.     return (ret);
  143.   } /* creat_if */
  144.  
  145.  
  146. int pascal open_if(fn)
  147.   char *fn;
  148.   {
  149.     int  ret;
  150.     ret = open(fn,O_RDWR|O_BINARY);
  151.     if (ret < 1) error(0,0L);
  152.     return (ret);
  153.   } /* open_if */
  154.  
  155.  
  156. void pascal close_if(handle)
  157.   int handle;
  158.   {
  159.     if(close(handle) < 0)  error(2,0L);
  160.   } /*  close_if */
  161.  
  162.  
  163. int cdecl open_index(name, pix, dup)
  164.   char *name;
  165.   IX_DESC *pix;
  166.   int dup;
  167.   {
  168.     pci = pix;
  169.     pci->ixfile = open_if(name);
  170.     pci->root_dirty = FALSE;
  171.     pci->duplicate = dup;
  172.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  173.     if (!cache_init)
  174.       {
  175.         init_cache();
  176.         cache_init = 1;
  177.       }
  178.     return ( IX_OK );
  179.   } /* open_index */
  180.  
  181.  
  182. void cdecl buffer_flush(pix)
  183.   IX_DESC *pix;
  184. {
  185.   int i;
  186.   if (pix->root_dirty)
  187.   {
  188.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  189.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  190.     pix->root_dirty = FALSE;
  191.   }
  192.   for (i = 0; i < NUM_BUFS; i++)
  193.   {
  194.     if ( (BUFHANDLE(i) == pix->ixfile) && BUFDIRTY(i) )
  195.     {
  196.       write_if(BUFHANDLE(i),
  197.            BUFBLOCK(i).brec,
  198.            (char *) &BUFBLOCK(i),
  199.            sizeof(BLOCK));
  200.       BUFDIRTY(i) = FALSE;
  201.     }
  202.   }
  203. }
  204.  
  205. void pascal reset_buffers(pix)
  206.   IX_DESC *pix;
  207.   {
  208.     int i;
  209.     for (i = 0; i < NUM_BUFS; i++)
  210.       if (BUFHANDLE(i) == pix->ixfile) BUFBLOCK(i).brec = NULLREC;
  211.   }
  212.  
  213.  
  214. int cdecl close_index(pix)
  215.   IX_DESC *pix;
  216.   {
  217.     int ret = IX_OK;
  218.     buffer_flush(pix);
  219.     reset_buffers(pix);
  220.     close_if(pix->ixfile);
  221.     return( ret );
  222.   } /* close_index */
  223.  
  224.  
  225. int cdecl make_index(name, pix, dup)
  226.   char *name;
  227.   IX_DESC *pix;
  228.   int dup;
  229.   {
  230.     pci = pix;
  231.     pci->ixfile = creat_if(name);
  232.     pci->duplicate = dup;
  233.     pci->root_dirty = FALSE;
  234.     pci->dx.nl = 1;
  235.     pci->dx.ff = NULLREC;
  236.     pci->level = 0;
  237.     CO(0) = -1;
  238.     CB(0) = 0L;
  239.     pci->root.brec = 0L;
  240.     pci->root.bend = 0;
  241.     pci->root.p0 = NULLREC;
  242.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  243.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  244.     if (!cache_init)
  245.       {
  246.         init_cache();
  247.         cache_init = 1;
  248.       }
  249.     return ( IX_OK );
  250.   } /* make_index */
  251.  
  252.  
  253. /*  cache I/O for BPLUS  */
  254.  
  255. void pascal update_block()
  256.   {
  257.     if (block_ptr == &(pci->root)) pci->root_dirty = TRUE;
  258.     else  BUFDIRTY(cache_ptr) = TRUE;
  259.   } /* update_block */
  260.  
  261.  
  262. void pascal init_cache()
  263.   {
  264.     register int  j;
  265.     for (j = 0; j < NUM_BUFS; j++)
  266.       {  BUFDIRTY(j) = 0;
  267.          BUFCOUNT(j) = 0;
  268.          BUFBLOCK(j).brec = NULLREC;
  269.       }
  270.   } /* init_cache */
  271.  
  272.  
  273. int pascal find_cache(r)
  274.   RECPOS r;
  275.   {
  276.     register int  j;
  277.     for (j = 0; j < NUM_BUFS; j++)
  278.       {
  279.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  280.          {  cache_ptr = j;
  281.             return (1);
  282.       }  }
  283.     return (-1);
  284.   } /* find_cache */
  285.  
  286.  
  287. int pascal new_cache()
  288.   {
  289.     register int  i;
  290.     i = (cache_ptr + 1) % NUM_BUFS;
  291.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  292.                               BUFBLOCK(i).brec,
  293.                               (char *) &BUFBLOCK(i),
  294.                               sizeof(BLOCK));
  295.     BUFHANDLE(i) = pci->ixfile;
  296.     BUFDIRTY(i) = 0;
  297.     return (i);
  298.   } /* new_cache */
  299.  
  300.  
  301. void pascal load_cache(r)
  302.   RECPOS r;
  303.   {
  304.     cache_ptr = new_cache();
  305.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  306.   } /* load_cache */
  307.  
  308.  
  309. void pascal get_cache(r)
  310.   RECPOS r;
  311.   {
  312.     if (find_cache(r) < 0)
  313.        load_cache(r);
  314.     block_ptr = &BUFBLOCK(cache_ptr);
  315.   } /* get_cache */
  316.  
  317.  
  318. void pascal retrieve_block(j, r)
  319.   int j;
  320.   RECPOS r;
  321.   {
  322.     if (j == 0)
  323.        block_ptr = &(pci->root);
  324.     else  get_cache(r);
  325.     CB(j) = block_ptr->brec;
  326.   } /* retrieve_block */
  327.  
  328.  
  329. /*  low level functions of BPLUS  */
  330.  
  331. int pascal prev_entry(off)
  332.   int off;
  333.   {
  334.      if (off <= 0)
  335.        {
  336.          off = -1;
  337.          CO(pci->level) = off;
  338.        }
  339.      else
  340.        off = scan_blk(off);
  341.      return(off);
  342.   } /* prev_entry */
  343.  
  344.  
  345. int pascal next_entry(off)
  346.   int off;
  347.   {
  348.      if (off == -1)
  349.        off = 0;
  350.      else
  351.        {
  352.          if (off < block_ptr->bend)
  353.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  354.        }
  355.      CO(pci->level) = off;
  356.      return (off);
  357.   } /* next_entry */
  358.  
  359.  
  360. void pascal copy_entry(to, from)
  361.   ENTRY *to;
  362.   ENTRY *from;
  363.   {
  364.     int me;
  365.     me = ENT_SIZE(from);
  366.     memcpy(to, from, me);
  367.   } /* copy_entry */
  368.  
  369.  
  370. int pascal scan_blk(n)
  371.   int n;
  372.   {
  373.      register int off, last;
  374.      off = 0;
  375.      last = -1;
  376.      while (off < n )
  377.        {  last = off;
  378.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  379.        }
  380.      CO(pci->level) = last;
  381.      return (last);
  382.   } /* scan_blk */
  383.  
  384.  
  385. int pascal last_entry()
  386.   {
  387.      return( scan_blk(block_ptr->bend) );
  388.   } /* last_entry */
  389.  
  390.  
  391. /*  maintain list of free index blocks  */
  392.  
  393. void pascal write_free(r, pb)
  394.   RECPOS r;
  395.   BLOCK *pb;
  396.   {
  397.     pb->p0 = FREE_BLOCK;
  398.     pb->brec = pci->dx.ff;
  399.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  400.     pci->dx.ff = r;
  401.   } /* write_free */
  402.  
  403.  
  404. RECPOS pascal get_free()
  405.   {
  406.     RECPOS  r, rt;
  407.  
  408.     r = pci->dx.ff;
  409.     if ( r != NULLREC )
  410.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  411.          pci->dx.ff = rt;
  412.       }
  413.     else
  414.       r = filelength (pci->ixfile);
  415.     return (r);
  416.   } /* get_free */
  417.  
  418.  
  419. /*  general BPLUS block level functions  */
  420.  
  421. int pascal find_block(pe, off, poff)
  422.   ENTRY *pe;
  423.   int *off;
  424.   int *poff;
  425.   {
  426.     register int pos, nextpos, ret;
  427.     pos = -1;
  428.     nextpos = 0;
  429.     ret = 1;
  430.     while ( nextpos < block_ptr->bend)
  431.       {
  432.         ret = strcmp((char *)(pe->key),
  433.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  434.     if (ret <= 0) break;
  435.         pos = nextpos;
  436.     nextpos += ENT_SIZE(ENT_ADR(block_ptr,pos));
  437.     /* nextpos = next_entry(pos); */
  438.       }
  439.     *poff = pos;
  440.     if (ret == 0) *off = nextpos;
  441.     else *off = pos;
  442.     CO(pci->level) = *off;
  443.     return (ret);
  444.   } /* find_block */
  445.  
  446.  
  447. void pascal movedown(pb, off, n)
  448.   BLOCK *pb;
  449.   int off;
  450.   int n;
  451.   {
  452.     memmove(ENT_ADR(pb, off),
  453.            ENT_ADR(pb, off + n),
  454.            pb -> bend - (off + n));
  455.   } /* movedown */
  456.  
  457.  
  458. void pascal moveup(pb, off, n)
  459.   BLOCK *pb;
  460.   int off;
  461.   int n;
  462.   {
  463.     memmove(ENT_ADR(pb, off + n),
  464.             ENT_ADR(pb, off),
  465.             pb->bend - off);
  466.   } /* moveup */
  467.  
  468.  
  469. void pascal ins_block(pb, pe, off)
  470.   BLOCK *pb;
  471.   ENTRY *pe;
  472.   int off;
  473.   {
  474.     int size;
  475.     size = ENT_SIZE(pe);
  476.     moveup(pb,off,size);
  477.     copy_entry(ENT_ADR(pb,off),pe);
  478.     pb->bend += size;
  479.   } /* ins_block */
  480.  
  481.  
  482. void pascal del_block(pb, off)
  483.   BLOCK *pb;
  484.   int off;
  485.   {
  486.     int ne;
  487.     ne = ENT_SIZE(ENT_ADR(pb, off));
  488.     movedown(pb, off, ne);
  489.     pb->bend -= ne;
  490.   } /* del_block */
  491.  
  492.  
  493. /*  position at start/end of index  */
  494.  
  495. int cdecl first_key(pe, pix)
  496.   ENTRY *pe;
  497.   IX_DESC *pix;
  498.   {
  499.     int ret;
  500.  
  501.     pci = pix;
  502.     block_ptr = &(pci->root);
  503.     CB(0) = 0L;
  504.     CO(0) = -1;
  505.     pci->level = 0;
  506.     while(block_ptr->p0 != NULLREC)
  507.       {
  508.         retrieve_block(++(pci->level), block_ptr->p0);
  509.         CO(pci->level) = -1;
  510.       }
  511.     ret = next_key(pe, pix);
  512.     return ( ret );
  513.   } /* first_key */
  514.  
  515.  
  516. int cdecl last_key(pe, pix)
  517.   ENTRY *pe;
  518.   IX_DESC *pix;
  519.   {
  520.     long  ads;
  521.     int   ret;
  522.  
  523.     pci = pix;
  524.     block_ptr = &(pci->root);
  525.     CB(0) = 0L;
  526.     pci->level = 0;
  527.     if(last_entry() >= 0)
  528.       {
  529.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  530.              retrieve_block(++(pci->level), ads);
  531.       }
  532.     CO(pci->level) = block_ptr->bend;
  533.     ret = prev_key(pe, pix);
  534.     return ( ret );
  535.   } /* last_key */
  536.  
  537.  
  538. /*  get next, previous entries  */
  539.  
  540. int cdecl next_key(pe, pix)
  541.   ENTRY *pe;
  542.   IX_DESC *pix;
  543.   {
  544.     RECPOS  address;
  545.     pci = pix;
  546.     retrieve_block(pci->level, CB(pci->level));
  547.     if(CO(pci->level) == -1) address = block_ptr->p0;
  548.     else
  549.      {
  550.        if (CO(pci->level) == block_ptr->bend) address = NULLREC;
  551.        else  address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  552.      }
  553.     while (address != NULLREC)
  554.       {
  555.          retrieve_block(++(pci->level), address);
  556.          CO(pci->level) = -1;
  557.          address = block_ptr->p0;
  558.       }
  559.     next_entry(CO(pci->level));
  560.     if (CO(pci->level) == block_ptr->bend)
  561.       {
  562.         do
  563.           { if(pci->level == 0)
  564.               {
  565.                 return (EOIX);
  566.               }
  567.             --(pci->level);
  568.             retrieve_block(pci->level, CB(pci->level));
  569.             next_entry(CO(pci->level));
  570.           } while (CO(pci->level) == block_ptr->bend);
  571.       }
  572.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  573.     return ( IX_OK );
  574.   } /* next_key */
  575.  
  576.  
  577. int cdecl prev_key(pe, pix)
  578.   ENTRY *pe;
  579.   IX_DESC *pix;
  580.   {
  581.     RECPOS  address;
  582.     pci = pix;
  583.     retrieve_block(pci->level, CB(pci->level));
  584.     prev_entry(CO(pci->level));
  585.     if (CO(pci->level) == -1)
  586.       address = block_ptr->p0;
  587.     else
  588.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  589.     if (address != NULLREC)
  590.       { do
  591.           {
  592.             retrieve_block(++(pci->level), address);
  593.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  594.           } while (address != NULLREC);
  595.       }
  596.     if (CO(pci->level) == -1)
  597.       { do
  598.           {
  599.             if(pci->level == 0)
  600.               {
  601.                 return (EOIX);
  602.               }
  603.             --(pci->level);
  604.           } while (CO(pci->level) == -1);
  605.         retrieve_block(pci->level, CB(pci->level));
  606.       }
  607.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  608.     return ( IX_OK );
  609.   } /* prev_key */
  610.  
  611.  
  612. /*  insert new entries into tree  */
  613.  
  614. void pascal split(l, pe, e)
  615.   int l;
  616.   ENTRY *pe;
  617.   ENTRY *e;
  618.   {
  619.     int  half, ins_pos, size;
  620.     ins_pos = CO(pci->level);
  621.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  622.     if (half == ins_pos)
  623.       *e = *pe;
  624.     else
  625.       {
  626.          copy_entry(e, ENT_ADR(block_ptr, half));
  627.          size = ENT_SIZE(e);
  628.          movedown(block_ptr, half, size);
  629.          block_ptr->bend -= size;
  630.       }
  631.     spare_block = &BUFBLOCK(new_cache());
  632.     memmove(spare_block->entries,
  633.            ENT_ADR(block_ptr,half),
  634.            block_ptr->bend - half);
  635.     spare_block->brec = get_free();
  636.     spare_block->bend = block_ptr->bend - half;
  637.     spare_block->p0 = e->idxptr;
  638.     block_ptr->bend = half;
  639.     e->idxptr = spare_block->brec;
  640.     if (ins_pos < half)
  641.       ins_block(block_ptr,pe,ins_pos);
  642.     else if (ins_pos > half)
  643.       {
  644.          ins_pos -= ENT_SIZE(e);
  645.          ins_block(spare_block,pe,ins_pos - half);
  646.          CB(l) = e->idxptr;
  647.          CO(l) = CO(l) - half;
  648.       }
  649.     write_if(pci->ixfile, spare_block->brec,
  650.              (char *) spare_block, sizeof(BLOCK));
  651.   } /* split */
  652.  
  653.  
  654. void pascal ins_level(l, e)
  655.   int l;
  656.   ENTRY *e;
  657.   {
  658.     int  i;
  659.     if ( l < 0)
  660.       {  for (i = 1; i < MAX_LEVELS; i++)
  661.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  662.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  663.            }
  664.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  665.          spare_block->brec = get_free();
  666.          write_if(pci->ixfile, spare_block->brec,
  667.                   (char *) spare_block, sizeof(BLOCK));
  668.          pci->root.p0 = spare_block->brec;
  669.          copy_entry((ENTRY *) (pci->root.entries), e);
  670.          pci->root.bend = ENT_SIZE(e);
  671.          CO(0) = 0;
  672.          pci->level = 0;
  673.      (pci->dx.nl)++;
  674.      pci->root_dirty = TRUE;
  675.       }
  676.     else ins_block(block_ptr,e,CO(l));
  677.   } /* ins_level */
  678.  
  679.  
  680. int pascal insert_ix(pe, pix)
  681.   ENTRY *pe;
  682.   IX_DESC *pix;
  683.   {
  684.     ENTRY    e, ee;
  685.     int h;
  686.     h = 0;
  687.     pci = pix;
  688.     ee = *pe;
  689.     do
  690.       {
  691.          if(CO(pci->level) >= 0)
  692.            CO(pci->level) +=
  693.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  694.          else
  695.            CO(pci->level) = 0;
  696.          update_block();
  697.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  698.            {
  699.              ins_level(pci->level, &ee);
  700.              break;
  701.            }
  702.          else
  703.            {
  704.              h = 1;
  705.              split(pci->level,&ee, &e);
  706.               ee = e;
  707.               pci->level--;
  708.               if (pci->level < 0)
  709.                 {
  710.                   ins_level(pci->level, &e);
  711.                   break;
  712.                 }
  713.               retrieve_block(pci->level, CB(pci->level));
  714.            }
  715.       }
  716.     while (1);
  717.     if (h) find_ix(pe, pix, 0);
  718.     return ( IX_OK );
  719.   } /* insert_ix */
  720.  
  721.  
  722. /*  BPLUS find and add key functions  */
  723.  
  724. int pascal find_ix(pe, pix, find)
  725.   ENTRY *pe;
  726.   IX_DESC *pix;
  727.   int find;
  728.   {
  729.     int      level, off, poff, ret;
  730.     int      savelevel, saveoff, h;
  731.     RECPOS   ads, saveads;
  732.     pci = pix;
  733.     ads = 0L;
  734.     level = 0;
  735.     h = 0;
  736.     ret = 0;
  737.     while (ads != NULLREC)
  738.       {  pci->level = level;
  739.          retrieve_block(level, ads);
  740.      ret = ret | !find_block(pe, &off, &poff); /* This change authorized by
  741.                                                   Gary Hunter on 6/14/91 and
  742.                                                   replaces the commented line
  743.                                                   below */
  744. /*     if (find_block(pe, &off, &poff) == 0) ret = 1;
  745.      else ret = 0;*/
  746.      if (ret && find && !pci->duplicate) break;
  747.      if(ret && pci->duplicate)
  748.      {
  749.        saveads = ads;
  750.        savelevel = level;
  751.        saveoff = off;
  752.        off = poff;
  753.        h = 1;
  754.      }
  755.          if (off == -1)
  756.            ads = block_ptr->p0;
  757.          else
  758.        ads = ENT_ADR(block_ptr, off)->idxptr;
  759.          CO(level++) = off;
  760.        }
  761.      if (h && find)
  762.      {
  763.        if (!ret)
  764.        {
  765.      retrieve_block(savelevel, saveads);
  766.      pci->level = savelevel;
  767.      ret = 1;
  768.        }
  769.        CO(savelevel) = saveoff;
  770.      }
  771.      return ( ret );
  772.    } /* find_ix */
  773.  
  774.  
  775. int cdecl find_key(pe, pix)
  776.   ENTRY *pe;
  777.   IX_DESC *pix;
  778.   {
  779.     int ret;
  780.     ret = find_ix(pe, pix, 1);
  781.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  782.     return ( ret );
  783.   } /* find_key */
  784.  
  785.  
  786. int cdecl add_key(pe, pix)
  787.   ENTRY *pe;
  788.   IX_DESC *pix;
  789.   {
  790.     int ret;
  791.     ret = find_ix(pe, pix, 0);
  792.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  793.     pe->idxptr = NULLREC;
  794.     return (insert_ix(pe, pix));
  795.   } /* add_key */
  796.  
  797.  
  798. int cdecl locate_key(pe, pix)
  799.   ENTRY *pe;
  800.   IX_DESC *pix;
  801.   {
  802.     int ret;
  803.     ret = find_ix(pe, pix, 1);
  804.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  805.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  806.     return ( ret );
  807.   } /* locate_key */
  808.  
  809.  
  810. int cdecl find_exact(pe, pix)
  811.   ENTRY *pe;
  812.   IX_DESC * pix;
  813.   {
  814.     int  ret;
  815.     ENTRY e;
  816.     copy_entry(&e, pe);
  817.     ret = find_key(&e, pix);
  818.     if ( ret && pci->duplicate)
  819.       {
  820.     while (e.recptr != pe->recptr)
  821.     {
  822.       if (next_key(&e, pci) == EOIX) return (0);   /* no more records */
  823.       if (strcmp(e.key, pe->key) != 0) return (0); /* key changed */
  824.     }
  825.       }
  826.     copy_entry(pe, &e);
  827.     return ( ret );
  828.   } /* find_exact */
  829.  
  830.  
  831. /* BPLUS delete key functions */
  832.  
  833. int cdecl delete_key(pe, pix)
  834.   ENTRY *pe;
  835.   IX_DESC *pix;
  836.   {
  837.      ENTRY   e;
  838.      RECPOS  ads;
  839.      int     h, leveli, levelf;
  840.      if (!find_exact(pe, pix))  return( IX_FAIL );
  841.      h = 1;
  842.      if ((ads = pe->idxptr) != NULLREC)
  843.        {
  844.           leveli = pci->level;
  845.           do
  846.             {
  847.                retrieve_block(++(pci->level), ads);
  848.                CO(pci->level) = -1;
  849.             }
  850.           while ((ads = block_ptr->p0) != NULLREC);
  851.           CO(pci->level) = 0;
  852.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  853.           levelf = pci->level;
  854.           pci->level = leveli;
  855.           replace_entry(&e);
  856.           pci->level = levelf;
  857.        }
  858.      while ( h )
  859.        {
  860.           retrieve_block(pci->level, CB(pci->level));
  861.           del_block(block_ptr, CO(pci->level));
  862.           update_block();
  863.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  864.           /* tree was reduced in height */
  865.             {
  866.               if (pci->root.p0 != NULLREC)
  867.                 {
  868.                   retrieve_block(++pci->level, pci->root.p0);
  869.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  870.                   (pci->dx.nl)--;
  871.                   write_free(block_ptr->brec, block_ptr);
  872.                   BUFDIRTY(cache_ptr) = 0;
  873.                   BUFHANDLE(cache_ptr) = 0;
  874.                 }
  875.               break;
  876.             }
  877.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  878.           if ( h )
  879.               h = combineblk(CB(pci->level), block_ptr->bend);
  880.        }
  881.     find_ix(pe,pix,0);
  882.     return( IX_OK );
  883.   } /* delete_key */
  884.  
  885.  
  886. int pascal combineblk(ads, size)
  887.   RECPOS ads;
  888.   int size;
  889.   {
  890.     ENTRY  e;
  891.     RECPOS address;
  892.     int    esize, off, ret, saveoff, ibuff;
  893.     ret = 0;
  894.     saveoff = CO(--(pci->level));
  895.     retrieve_block(pci->level, CB(pci->level));
  896.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  897.       /* combine with page on right */
  898.       {
  899.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  900.           {
  901.             copy_entry(&e, ENT_ADR(block_ptr, off));
  902.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  903.             retrieve_block(++pci->level, address);
  904.             ibuff = cache_ptr;
  905.             spare_block = block_ptr;
  906.             retrieve_block(pci->level, ads);
  907.             esize = ENT_SIZE(&e);
  908.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  909.                  && (spare_block->bend <= block_ptr->bend + esize))
  910.                return( ret );
  911.             e.idxptr = spare_block->p0;
  912.             ins_block(block_ptr, &e, block_ptr->bend);
  913.             update_block();
  914.             if ((block_ptr->bend + spare_block->bend) < split_size)
  915.             /* combine the blocks */
  916.               {
  917.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  918.                        ENT_ADR(spare_block, 0),
  919.                        spare_block->bend);
  920.                 block_ptr->bend += spare_block->bend;
  921.                 write_free(spare_block->brec, spare_block);
  922.                 BUFDIRTY(ibuff) = 0;
  923.                 BUFHANDLE(ibuff) = 0;
  924.                 --pci->level;
  925.                 ret = 1;
  926.               }
  927.             else
  928.             /* move an entry up to replace the one moved */
  929.               {
  930.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  931.                 esize = ENT_SIZE(&e);
  932.                 movedown(spare_block, 0, esize);
  933.                 spare_block->bend -= esize;
  934.                 spare_block->p0 = e.idxptr;
  935.                 BUFDIRTY(ibuff) = 1;
  936.                 --(pci->level);
  937.                 replace_entry(&e);
  938.               }
  939.           }
  940.       }
  941.     else
  942.       /* move from page on left */
  943.       {
  944.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  945.                  < split_size)
  946.           {
  947.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));
  948.             off = prev_entry(saveoff);
  949.             if (CO(pci->level) == -1) address = block_ptr->p0;
  950.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  951.             retrieve_block(++pci->level, address);
  952.             off = last_entry();
  953.             ibuff = cache_ptr;
  954.             spare_block = block_ptr;
  955.             retrieve_block(pci->level, ads);
  956.             esize = ENT_SIZE(&e);
  957.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  958.                  && (spare_block->bend <= block_ptr->bend + esize))
  959.                return( ret );
  960.             BUFDIRTY(ibuff) = 1;
  961.             CO(pci->level) = 0;
  962.             e.idxptr = block_ptr->p0;
  963.             ins_block(block_ptr, &e, 0);
  964.             if ((block_ptr->bend + spare_block->bend) < split_size)
  965.             /* combine the blocks */
  966.               {
  967.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  968.                        ENT_ADR(block_ptr, 0),
  969.                        block_ptr->bend);
  970.                 spare_block->bend += block_ptr->bend;
  971.                 write_free(block_ptr->brec, block_ptr);
  972.                 BUFDIRTY(cache_ptr) = 0;
  973.                 BUFHANDLE(cache_ptr) = 0;
  974.                 CO(--(pci->level)) = saveoff;
  975.                 ret = 1;
  976.               }
  977.             else
  978.             /* move an entry up to replace the one moved */
  979.               {
  980.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  981.                  copy_entry(&e, ENT_ADR(spare_block, off));
  982.                  spare_block->bend = off;
  983.                  update_block();
  984.                  CO(--(pci->level)) = saveoff;
  985.                  replace_entry(&e);
  986.               }
  987.           }
  988.       }
  989.     return ( ret );
  990.   } /* combineblk */
  991.  
  992.  
  993. void pascal replace_entry(pe)
  994.   ENTRY *pe;
  995.   {
  996.     retrieve_block(pci->level, CB(pci->level));
  997.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  998.     del_block(block_ptr, CO(pci->level));
  999.     prev_entry(CO(pci->level));
  1000.     insert_ix(pe, pci);
  1001.     update_block();
  1002.   } /* replace_entry */
  1003.  
  1004.